import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//三数之和
//测试链接 https://leetcode.cn/problems/3sum/
public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();  //保存结果
        int n = nums.length-1; //数组最后一个下标

        for(int i = 0; i <= n - 2;){
            int num = nums[i];
            if(num > 0) break;  //小优化
            int target = -num;   //两数之和为-num
            int left = i+1, right = n;

            System.out.println(left + " " + right);
            while(left < right){
                int l = nums[left];
                int r = nums[right];

                if(l + r > target){
                    right--;
                }else if(l + r < target){
                    left++;
                }else{ //找到和为-num的值了
                    ans.add(new ArrayList<Integer>(Arrays.asList(num,nums[left],nums[right])));

                    left++; right--;
                    //去重
                    while(left <= n && nums[left] == l) left++;
                    while(right > i && nums[right] == r)right--;
                }
            }
            i++;
            //去重
            while(i <= n &&  nums[i] == num ){
                i++;
            }
        }

        return ans;
    }
}
